class Solution 
{
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) 
    {
        // 1. 准备工作
        unordered_map<int, vector<int>> edges;  // 邻接表存图
        vector<int> in(numCourses);  // 标记每一个顶点的入度

        // 2. 建图
        for(auto& e : prerequisites)
        {
            int a = e[0], b = e[1]; // b -> a 的一条边
            edges[b].push_back(a);  // b a
            in[a]++;    // 统计对应顶点的入度
        }

        // 3. 拓扑排序
        queue<int> q;
        // (1) 把所有入度为 0 的点加入到队列中
        for(int i = 0; i < numCourses; i++)
        {
            if(in[i] == 0)
                q.push(i);
        }

        // (2) bfs
        while(q.size())
        {
            int t = q.front(); q.pop();

            // 修改入度
            for(int a : edges[t])
            {
                in[a]--;
                if(in[a] == 0)
                    q.push(a);
            }
        }

        // 4. 判断是否有环
        for(int i = 0; i < numCourses; i++)
            if(in[i])   // 入度不为 0，说明有环
                return false;
            
        return true;
    }
};